package cn.dapeng.tree.binary;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 判断一棵树是否是完全二叉树
 * <p>
 * 1. 如果一颗树，有右孩子，但没有左孩子，肯定不是完全二叉树
 * 2. 依次遍历二叉树的每一个节点，
 * 2.1 假设节点X，左右节点双全，继续往下遍历
 * 2.2 当第一次遍历到某个节点只有左孩子，没有有孩子，接下来遍历的所有节点都必须是叶子节点
 */
public class CheckCompleteBinaryTree {

    /**
     * 按层遍历方式
     */
    public static boolean isCompleteTree(TreeNode x) {
        if (x == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(x);

        boolean isLeaf = false;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                x = queue.poll();

                if (x.left != null) {
                    queue.add(x.left);
                }

                if (x.right != null) {
                    queue.add(x.right);
                }

                // 第一种判断
//                if (x.left == null && x.right != null) {
//                    return false;
//                } else if (x != null && x.right != null) {
//
//                } else {
//                    if (!isLeaf) {
//                        isLeaf = true;
//                    } else {
//                        return false;
//                    }
//                }

                // 第二种判断，这种处理逻辑更紧凑
                if ((isLeaf && (x.left != null || x.right != null)) || (x.left == null && x.right != null)) {
                    return false;
                }

                if (x.left == null && x.right == null) {
                    isLeaf = true;
                }
            }
        }
        return true;
    }

    /**
     * 递归实现方式
     * @param head
     * @return
     */
    public static boolean isBTS(TreeNode head) {
        return process(head).isCBT;
    }

    public static Info process(TreeNode head) {
        if (head == null) {
            return new Info(true, true, 0);
        }

        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);

        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        boolean isBST = false;
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        if (isFull) {
            isBST = true;
        } else {

            if (leftInfo.isFull && rightInfo.isFull && (leftInfo.height == rightInfo.height + 1)) {
                isBST = true;
            }

            if (leftInfo.isFull && rightInfo.isCBT && (leftInfo.height == rightInfo.height + 1)) {
                isBST = true;
            }

            if (leftInfo.isCBT && rightInfo.isFull && (leftInfo.height == rightInfo.height + 1)) {
                isBST = true;
            }
        }

        return new Info(isFull, isBST, height);
    }

    public static class Info {
        public int height;
        public boolean isFull;
        public boolean isCBT;

        public Info(boolean isFull, boolean isCBT, int height) {
            this.isFull = isFull;
            this.isCBT = isCBT;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(0);

        head.left = new TreeNode(1);
        head.right = new TreeNode(4);
        head.right.left = new TreeNode(2);
        head.right.right = new TreeNode(2);

        head.left.left = new TreeNode(3);
        head.left.right = new TreeNode(11);
        head.left.right.left = new TreeNode(3);

        System.out.println(isCompleteTree(head));

        System.out.println(isBTS(head));
    }
}
